二分图的建图

闲话

主要收集一些建图比较有特点的题,也具有一定的套路性.见多识广,写题解加深一下印象.

[POJ 3041] Asteroids

原题链接:[POJ 3041] Asteroids
题目大意:有一个nmn*m的的格子,每个格子里可能有一个敌人,一共有kk个敌人.现在有一个武器可以消灭整行或整列的敌人,问你最少要使用多少次这个武器才能消灭所有的敌人.

数据范围:
1N5001 \leq N \leq 500
1K100001 \leq K \leq 10000

思路

武器是每一行每一列的消灭敌人的,对于一个敌人来说,他如果能被竖着的武器消灭就一定不会再打一个横着的武器,因为这没有意义.如果把整行整列看做是一个点,而一个敌人看做是两个点相连的话,那么整个问题就会变成一个最小顶点覆盖问题.因为要选的就是哪一行哪一列去消灭敌人,其次每个敌人都要消灭,因此就是在这张图上选出最少的点,使每条边都被覆盖.可以验证这是一张二分图,把左部点设置成行的坐标,右部点设置成列的坐标,对列做一个映射把下标增加nn.之后就可以在这张图上跑最大匹配了,因为对于二分图来说最小顶点覆盖和最大匹配的数量是相等的.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005,M = 2e5+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N];
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	scanf("%d%d",&n,&m);
	s = 0;t = 2 * n + 2;
	for(int i = 1;i <= n;++i)	add(s,i,1),add(i + n,t,1);
	for(int i = 0;i < m;++i)
	{
		int x,y;scanf("%d%d",&x,&y);
		add(x,y + n,1);
	}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	printf("%lld",maxflow);
    return 0;
}

[POJ 3281] Dining

题目大意:一共有nn个人,每个人有自己喜欢的食物和饮料.而每种食物和饮料最多只能分配给一个人.问最多有多少个人可以同时拿到自己喜欢的食物和饮料.输出数量即可.

数据范围:
1n1001 \leq n \leq 100
1F,D1001 \leq F,D \leq 100

思路

假设说没有饮料,那么这个问题就非常的普通,就是一个人与食物的最大匹配问题.但是现在多加了一个饮料,这就导致问题看起来变的难缠了.这个题的关键就是转换,把一个人与两个匹配变成两个人跟两个匹配.
首先把所有人拆点,每个人分两个,左边的连食物,右边的连饮料,拆完点之后的人之间自己与自己相连.如下图
之后在两边加一个源点和汇点.那么这张图上的一条流就是一个人匹配两个食物的形式.把所有的容量都设置成11,就保证了所有食物和饮料都只使用了一次.最后在原图上求解最大匹配等价于在新图上求解最大流.套模板即可.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 405,M = 1e6+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N],F,D;
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	scanf("%d%d%d",&n,&F,&D);
	s = 0,t = F + 2 * n + D + 1;
	for(int i = 1;i <= F;++i)	add(s,i,1);
	for(int i = 1;i <= n;++i)
	{
		int _f,_d;scanf("%d%d",&_f,&_d);
		while(_f--)
		{
			int x;scanf("%d",&x);
			add(x,i + F,1);
		}
		while(_d--)
		{
			int x;scanf("%d",&x);
			add(i + n + F,x + F + 2 * n,1);
		}
		add(i + F,i + n + F,1);
	}
	for(int i = 1;i <= D;++i)	add(i + F + 2 * n,t,1);
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	printf("%lld",maxflow);
    return 0;
}